package bird.linkedlist;

/**
 * @author sijunqiang
 * @data 2021/5/23 15:35
 * @description: 链表
 */
public class LinkedList<E> {

    // dummyHead-一个虚拟的头节点 主要的作用是指向第一个链表中的节点。
    private Node dummyHead;
    // size-代表链表存储的元素个数
    private int size;

    // 内部节点 链表中数据真正存储的地方
    private class Node {
        // 真正存储元素的地方
        public E data;

        // 指向下一个节点的指针 若指向下一个节点的指针为null 说明是链尾
        public Node next;


        public Node(E e, Node next) {
            this.data = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    // construct function
    public LinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

//+++++++++++++++++add++++++

    /**
     * 思路：
     * :第一,先去找到需要插入指定位置的节点的前一个节点.
     * :第二, 再去创建一个新的节点插入指定的位置。
     */
    public void add(int index, E e) {
        //第一，先判断索引是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add fail! index is illegal!");
        }

        // 根据指针递进 直到找到需要添加的哪个索引的前一个位置
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //  第三，插入节点
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    //++++++++get++++++++++
    public E get(int index) {
        //先校验
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("get fail! index is illegal!");
        }

        // 先遍历找到这个节点
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;// 指针递进的方式寻找
        }
        return cur.data;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size);
    }

    //+++++++++++++++++++set+++
    public E set(int index, E e) {
        // 先校验
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("set fail! index is illegal!");
        }
        // 先找到这个索引所在的节点
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        E ret = cur.data;
        cur.data = e;
        return ret;
    }

    public E setFirst(E e) {
        return set(0, e);
    }

    public E setLast(E e) {
        return set(size, e);
    }

    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur.next != null) {
            if (cur.data.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //+++++remove+++++++++

    // 删除的思想-- 找到待删除的索引前一个节点 然后将这个位置的next 指向需要删除的节点的next.
    public E remove(int index) {

        // 先校验
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("remove fail! index is illegal!");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node delNode = prev.next;//待删除的节点
        prev.next = delNode.next;// 将待删除的节点指针赋值给待删除的节点的前一个节点指针
        delNode.next = null;// 将待删除的节点删除
        size--;
        return delNode.data;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        // size-1 代表的意思是 待删除的节点的前一个节点
        return remove(size-1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("linkedList: ");
        for (Node node = dummyHead.next; node != null; node = node.next) {
            res.append(node.data);
            res.append("-->");
        }
        res.append("NULL");
        return res.toString();
    }
}

